package org.cabbage.lintcode;

/**
 * 在数组中找到第k大的元素
 * <p>
 * 注意事项
 * <p>
 * 你可以交换数组中的元素的位置
 * <p>
 * 您在真实的面试中是否遇到过这个题？ Yes 样例 给出数组 [9,3,2,4,8]，第三大的元素是 4
 * <p>
 * 给出数组 [1,2,3,4,5]，第一大的元素是 5，第二大的元素是 4，第三大的元素是 3，以此类推
 * <p>
 * 挑战 要求时间复杂度为O(n)，空间复杂度为O(1)
 * <p>
 * 标签 相关题目
 *
 * @author gezhangyuan
 */
public class BigK {
    public static void main(String[] args) {
        int r = kthLargestElement(3, new int[]{2, 5, 3, 0, 2, 3, 0, 3});
        System.out.println(r);
    }

    public static int kthLargestElement(int k, int[] nums) {
        int[] b = new int[nums.length];
        int max = getMaxNumber(nums);
        int[] c = new int[max + 1];
        for (int i = 0; i < max; i++) {
            c[i] = 0;
        }
        for (int i = 0; i < nums.length; i++) {
            c[nums[i]]++;
        }

        for (int i = 1; i <= max; i++) {
            c[i] += c[i - 1];
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            b[c[nums[i]] - 1] = nums[i];
            c[nums[i]]--;
        }
        return b[b.length - k];
    }

    public static int getMaxNumber(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
            }
        }
        return max;
    }

}
